The process of encryption converts ordinary information (referred to as “plaintext”) into “ciphertext,” which is unintelligible to anyone except those possessing special knowledge such as a key or possibly to a cryptanalyst. Decryption is the reverse process, converting ciphertext back to plaintext. Encryption and decryption are collectively referred to as “ciphering.” Various algorithms—known as “ciphers”—are used for encryption and the reverse decryption process. The cipher uses a secret parameter, known as a “key,” in carrying out the encryption and decryption processes. In the context of the present patent application and in the claims, the terms “key” and “cryptographic key” are used interchangeably, and it will be understood that in general, cryptographic keys may be used for both encryption and decryption as well as other cryptographic operations, for example, but not limited to, producing and verifying digital signatures.
Various types of ciphers are known in the art, including both symmetric and asymmetric types. In an asymmetric cipher, data are encrypted using a public key, which can be known to everyone. The resulting ciphertext can be decrypted only using a complementary private key, which is generally kept secret. Public/private key pairs can also be used to generate and verify digital certificates (or signatures). In the case of a digital certificates (or signature), the private key is used in a cryptographic operation operating on certain data to produce a digital certificate (signature), and the public key is used to verify the identity of the encrypting party. The term “cryptographic operation” is used herein generally to refer to both encryption/decryption and to digital signature generation/verification.
One of the most commonly used asymmetric ciphers is the Rivest Shamir Adleman (RSA) algorithm, which is described, for example, in U.S. Pat. No. 4,405,829. A pair of prime numbers, p and q, is used to generate the public and private keys, which have the form (n,e) and (n,d), respectively. Here n is referred to as the modulus and e and d are referred to as the exponents. The modulus n is simply the product of the prime numbers: n=pq. The public exponent e is an integer in the range 1≦e≦φ(pq), wherein the totient φ(pq)=(p−1)(q−1). The private exponent d is computed to satisfy the congruence relation de=1(mod φ(pq)). Various methods and criteria are known in the art for choosing the primes and exponents, but they are beyond the scope of the present patent application. The security of encryption typically increases with the length of the modulus that is used. Therefore, it is now common in RSA encryption to use private keys with moduli and exponents that are 1024 bits or even longer.
Normally, public and private keys (or the prime numbers that are used to compute them) are stored in a computer memory belonging to the private key holder. Krivoruchko et al. point out certain risks in this approach, in “Storing RSA Private Keys in Your Head,” 12th Pacific Rim International Symposium on Dependable Computing PRDC '06 (2006), pages 129-138. The authors note, for example, that an unauthorized party may gain access to the device in which the private key is stored and thus be able to steal the private key. In response to this problem, the authors describe a way of generating a public/private RSA key pair from a passphrase that a human user can remember and input to a computing device when needed.